#ifndef _NODE_
#define _NODE_ 1

#include <cstdint>
#include <stdio.h>
#include <stdlib.h>

// 打印
void indent(uint32_t level) {
    for (uint32_t i = 0; i < level; i++) {
    printf("  ");
    }
}

/* 
 *  由于 B+Tree 含有两种不同结构的节点(Internal Node & Leaf Node)
 *  所以通过 void* 实现 (教程不用联合体, 个人猜测是因为直接用指针比较容易实现序列化和反序列化)
 *  要获取对应数据的值, 也通过 地址+偏移 来寻址并读取
 * 
 *  每一张 page 储存一个 Node, 由于不同类型的 Node 的大小不一
 *  所以 page 后面剩余的字节也不相同
 * 
 *  # internal node layers	  max leaf nodes        Size of all leaf nodes
 *            0                   511^0 = 1                  4   KB
 *            1                   511^1 = 512               ~2   MB
 *            2                   511^2 = 261,121           ~1   GB
 *            3                   511^3 = 133,432,831       ~550 GB
 */

enum class NodeType {
    Internal,
    Leaf
};

/*
 * Common Node Header Layout
 *
 * Common Node Headr {
 * NodeType NodeType;
 * uint8_t  is_root;
 * void*    parent_pointer;
 * }
 * 
 */
const uint32_t NODE_TYPE_SIZE = sizeof(NodeType);
const uint32_t NODE_TYPE_OFFSET = 0;
const uint32_t IS_ROOT_SIZE = sizeof(uint8_t);
const uint32_t IS_ROOT_OFFSET = NODE_TYPE_SIZE;
const uint32_t PARENT_POINTER_SIZE = sizeof(uint32_t);
const uint32_t PARENT_POINTER_OFFSET = IS_ROOT_OFFSET + IS_ROOT_SIZE;
const uint8_t COMMON_NODE_HEADER_SIZE =
    NODE_TYPE_SIZE + IS_ROOT_SIZE + PARENT_POINTER_SIZE;

namespace Node {
    inline NodeType get_node_type(void* node) {
        uint8_t value = *((uint8_t*) (node + NODE_TYPE_OFFSET));
        return (NodeType) value;
    }

    void set_node_type(void* node, NodeType type) {
        uint8_t value = (uint8_t) type;
        *((uint8_t*) (node + NODE_TYPE_OFFSET)) = value;
    }

    bool is_root(void* node) {
        return (bool) *((uint8_t*)node + IS_ROOT_OFFSET);
    }

    void set_node_root(void* node, bool is_root) {
        uint8_t value = is_root;
        *((uint8_t*) (node + IS_ROOT_OFFSET)) = value;
    }

    uint32_t get_max_key(void* node); // 定义在下面
}


/*
 * Leaf Node Layout
 *
 * Leaf Node {
 * NodeType NodeType;
 * uint8_t  is_root;
 * void*    parent_pointer;            Common Node Header
 * -----------------------------------
 * uint32_t num_cells;                 Leaf Node Header
 * -----------------------------------
 * Cell     cells[LEAF_NODE_MAX_CELLS] Leaf Node Body
 * }
 * 
 */

/*
 * Cell layout
 *
 * Cell {
 * uint32_t key;
 * Row      value;
 * }
 * 
 */

/*
 * Leaf Node Header layout
 */
const uint32_t LEAF_NODE_NUM_CELLS_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_NUM_CELLS_OFFSET = COMMON_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_HEADER_SIZE =
    COMMON_NODE_HEADER_SIZE + LEAF_NODE_NUM_CELLS_SIZE;

/*
 * Leaf Node Body Layout
 */
const uint32_t LEAF_NODE_KEY_SIZE = sizeof(uint32_t);
const uint32_t LEAF_NODE_KEY_OFFSET = 0;
const uint32_t LEAF_NODE_VALUE_SIZE = 293U;
const uint32_t LEAF_NODE_VALUE_OFFSET =
    LEAF_NODE_KEY_OFFSET + LEAF_NODE_KEY_SIZE;
const uint32_t LEAF_NODE_CELL_SIZE = LEAF_NODE_KEY_SIZE + LEAF_NODE_VALUE_SIZE;
const uint32_t LEAF_NODE_SPACE_FOR_CELLS = 4096U - LEAF_NODE_HEADER_SIZE;
const uint32_t LEAF_NODE_MAX_CELLS =
    LEAF_NODE_SPACE_FOR_CELLS / LEAF_NODE_CELL_SIZE;

// 为了使 B+树 保持平衡所设置的、拆分节点的数据
// 可以证明 LEAF_NODE_LEFT_SPLIT_COUNT >= LEAF_NODE_RIGHT_SPLIT_COUNT
const uint32_t LEAF_NODE_RIGHT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) / 2;
const uint32_t LEAF_NODE_LEFT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) - LEAF_NODE_RIGHT_SPLIT_COUNT;

void print_constants() {
  printf("ROW_SIZE: %d\n", 293U);
  printf("COMMON_NODE_HEADER_SIZE: %d\n", COMMON_NODE_HEADER_SIZE);
  printf("LEAF_NODE_HEADER_SIZE: %d\n", LEAF_NODE_HEADER_SIZE);
  printf("LEAF_NODE_CELL_SIZE: %d\n", LEAF_NODE_CELL_SIZE);
  printf("LEAF_NODE_SPACE_FOR_CELLS: %d\n", LEAF_NODE_SPACE_FOR_CELLS);
  printf("LEAF_NODE_MAX_CELLS: %d\n", LEAF_NODE_MAX_CELLS);
}

namespace LeafNode {
    inline uint32_t* get_num_cells(void* node) {
        return (uint32_t*) (node + LEAF_NODE_NUM_CELLS_OFFSET);
    }

    inline void* get_cell(void* node, uint32_t cell_num) {
        return node + LEAF_NODE_HEADER_SIZE + cell_num * LEAF_NODE_CELL_SIZE; 
    }

    inline uint32_t* get_key(void* node, uint32_t cell_num) {
        return (uint32_t*) get_cell(node, cell_num);
    }

    inline void* get_value(void* node, uint32_t cell_num) {
        return get_cell(node, cell_num) + LEAF_NODE_KEY_SIZE;
    }

    void initialize(void* node) {
        Node::set_node_type(node, NodeType::Leaf);
        Node::set_node_root(node, false);
        *get_num_cells(node) = 0;
    }
}

/*
 * Internal Node {
 * NodeType NodeType;
 * uint8_t  is_root;
 * void*    parent_pointer;            Common   Node Header
 * -----------------------------------
 * uint32_t num_keys;    // cell 的数量
 * uint32_t right_child; // 最右边的    Internal Node Header
 * ----------------------------------- 
 * Cell     cells[..];                 Internal Node Body
 * }
 * 
 * cell {
 * uint32_t key;
 * uint32_t child; // 因为一个 page 就是一个 Node, 所以不记录指针而是记录 pageNUm
 * }
 *
 */

/*
 * Internal Node Header Layout
 */
const uint32_t INTERNAL_NODE_NUM_KEYS_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_NUM_KEYS_OFFSET = COMMON_NODE_HEADER_SIZE;
const uint32_t INTERNAL_NODE_RIGHT_CHILD_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_RIGHT_CHILD_OFFSET =
    INTERNAL_NODE_NUM_KEYS_OFFSET + INTERNAL_NODE_NUM_KEYS_SIZE;
const uint32_t INTERNAL_NODE_HEADER_SIZE = COMMON_NODE_HEADER_SIZE +
                                           INTERNAL_NODE_NUM_KEYS_SIZE +
                                           INTERNAL_NODE_RIGHT_CHILD_SIZE;
/*
 * Internal Node Body Layout
 */
const uint32_t INTERNAL_NODE_KEY_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_CHILD_SIZE = sizeof(uint32_t);
const uint32_t INTERNAL_NODE_CELL_SIZE =
    INTERNAL_NODE_CHILD_SIZE + INTERNAL_NODE_KEY_SIZE;

namespace InternalNode {
    uint32_t* get_num_keys(void* node) {
        return (uint32_t*) (node + INTERNAL_NODE_NUM_KEYS_OFFSET);
    }

    uint32_t* get_right_child(void* node) {
        return (uint32_t*) (node + INTERNAL_NODE_RIGHT_CHILD_OFFSET);
    }

    uint32_t* get_cell(void* node, uint32_t cell_num) {
        return (uint32_t*) (node + INTERNAL_NODE_HEADER_SIZE + cell_num * INTERNAL_NODE_CELL_SIZE);
    }

    uint32_t* get_child(void* node, uint32_t child_num) {
        uint32_t num_keys = *get_num_keys(node);
        if (child_num > num_keys) {
            printf("Tried to access child_num %d > num_keys %d\n", child_num, num_keys);
            exit(1);
        } else if (child_num == num_keys) {
            return get_right_child(node);
        } else {
            return get_cell(node, child_num);
        }
    }

    uint32_t* get_key(void* node, uint32_t key_num) {
        return (uint32_t*) (get_cell(node, key_num) + INTERNAL_NODE_CHILD_SIZE);
    }

    void initialize(void* node) {
        Node::set_node_type(node, NodeType::Internal);
        Node::set_node_root(node, false);
        *InternalNode::get_num_keys(node) = 0;
    }
}

namespace Node {
    uint32_t get_max_key(void* node) {
        switch (get_node_type(node))
        {
        case NodeType::Internal:
            return *InternalNode::get_key(node, *InternalNode::get_num_keys(node) - 1);
        case NodeType::Leaf:
            return *LeafNode::get_key(node, *LeafNode::get_num_cells(node) - 1);
        default:
            printf("Error: valid date file.\n");
            break;
        }
        return -1;
    }
}

#endif